class TreeNode():
    def __init__(self, data,leftChild=None,rightChild = None):
        self.data = data
        self.leftChild = leftChild
        self.rightChild = rightChild

#
class TreeBase():
    def __init__(self):
        self.root = None

class MyBinaryTree():
    def __init__(self):
        self.root = None
        pass
    def CreateTreeByArr(self,nodeList):
        i = 0
        length = len(nodeList)

        while(i<length):
            nodeTemp = TreeNode(nodeList[i])
            self.root = self.InsertNode(self.root,nodeTemp)
            self.PrintTree()
            i = i+1
        pass

    #获取一课树的高度
    def GetTreeHeight(self,root):
        if root == None:
            return 0
        else:
            leftHeight = self.GetTreeHeight(root.leftChild)
            rightHeight = self.GetTreeHeight(root.rightChild)
        if leftHeight > rightHeight:
            return leftHeight + 1
        else:
            return rightHeight + 1


    #插入一个节点
    def InsertNode(self,root,node,FatherNode = None):
        if root == None:
            root = node
        else:
            if node.data>root.data:
                root.rightChild = self.InsertNode(root.rightChild,node,root)
            else:
                root.leftChild = self.InsertNode(root.leftChild,node,root)
            
            leftTreeHeight = self.GetTreeHeight(root.leftChild)
            rightTreeHeight = self.GetTreeHeight(root.rightChild)
            if leftTreeHeight - rightTreeHeight > 1:
                if node.data<root.leftChild.data:
                    root = self.LL(root);
                else:
                    root = self.LR(root)
            else:
                if rightTreeHeight - leftTreeHeight > 1:
                    if node.data>root.rightChild.data:
                        root = self.RR(root)
                    else:
                        root = self.RL(root)
                else:
                    #此时以root为根的树应该是平衡的，不需要调整
                    pass
        
        return root

        pass

    #单左旋
    def LL(self,root,rootFather = None):
        print("LL")
        rootTemp = root
        root = root.leftChild
        rootTemp.leftChild = root.rightChild
        root.rightChild = rootTemp
        return root
    def RR(self,root):
        print("RR")
        rootTemp = root
        root = root.rightChild
        rootTemp.rightChild = root.leftChild
        root.leftChild = rootTemp
        return root
    #双左旋
    def LR(self,root,rootFather=None):
        print("LR")
        #第一次旋转
        root.leftChild = self.RR(root.leftChild)
        #第二次旋转
        root = self.LL(root)
        return root
    #双右旋
    def RL(self,root,rootFather=None):
        print("RL")
        #第一次旋转
        root.rightChild = self.LL(root.rightChild)
        #第二次旋转
        root = self.RR(root)
        return root


    def PrintTree(self):

        if self.root == None:
            print("No Tree")
            return
        list = []
        listIndex = 0
        list.append(self.root)
        while(listIndex<len(list)):
            if list[listIndex].leftChild != None:
                list.append(list[listIndex].leftChild)
            if list[listIndex].rightChild != None:
                list.append(list[listIndex].rightChild)
            listIndex = listIndex+1
    
        treeCount = listIndex*2

        list = []
        listIndex = 0
        list.append(self.root)

        while(listIndex<treeCount):
            #print("%d,"%(list[listIndex].data),end = "")
            #if list[listIndex].data != "  " and ((list[listIndex].leftChild != None) or (list[listIndex].rightChild != None)):
            #if list[listIndex].data != "  ":
            if list[listIndex].leftChild != None:
                list.append(list[listIndex].leftChild)
            else:
                list.append(TreeNode("  "))
            if list[listIndex].rightChild != None:
                list.append(list[listIndex].rightChild)
            else:
                list.append(TreeNode("  "))
            listIndex = listIndex+1

        listIndex = 0
        listLen = len(list)
        listMaxNum = (listLen+1)/2
        #listMaxNum = (listLen+1)
        levelNum = 0
        levelMax = 1
        #print(listMaxNum)

        while(listIndex<listLen):
            levelNum = levelNum + 1
            speaceNum = listMaxNum*3/2

            i = 0
            while(i<speaceNum-3):
                print(" ",end = "")
                i = i + 1
            print("%3s"%(list[listIndex].data),end = "")
            i =0
            while(i<speaceNum):
                print(" ",end = "")
                i = i + 1
            listIndex = listIndex + 1
        
            if levelNum < levelMax:
                pass
            else:
                listMaxNum = listMaxNum/2
                levelMax = levelMax*2
                levelNum = 0
                print("")
                speaceNum = listMaxNum*3/2
        print("")
    
    #endregion